// Copyright 2006 Mloofle Inc. All Rights Reserved.
// Developed via Cleanroom
import java.util.BitSet;

/**
 * Parses a list of arguments into a logical query structure.
 */
public class QueryParser {
  /*
   * INVARIANTS: This class encapsulates an algorithm and has no state.
   */

  /**
   * Thrown when a syntax error is encountered while parsing a query.
   */
  public static class QuerySyntaxError extends Exception {
  }

  /**
   * Encapsulates the process of reading tokens in a controlled manner.
   */
  private static class TokenStream {
    /*
     * INVARIANTS
     * 
     * 0 <= next <= tokens.length
     * 
     * (next == tokens.length) implies end of stream
     */

    /**
     * Constructs a new token stream from an array of tokens.
     */
    public TokenStream(String[] tokens) {
      // PRE: tokens is non-null
      this.tokens = tokens;
      this.next = 0;
      // POST: tokens field is initialized
      // POST: next points to the first token to be returned, or end of steam if
      // tokens.length == 0
    }

    /**
     * Returns whether the stream is at the end. If the stream is at the end, no
     * more tokens may be read.
     * 
     * @return <code>true</code> if the stream is at the end
     */
    public boolean isEndOfStream() {
      return next == tokens.length;
    }

    /**
     * Looks at the next value to be read from the stream without consuming it.
     * 
     * @return the next token to be read
     * @throws IndexOutOfBoundsException if the stream is at the end
     */
    public String peek() {
      if (isEndOfStream()) {
        throw new IndexOutOfBoundsException();
      }
      return tokens[next];
    }

    /**
     * Reads and consumes the next value to be read from the stream.
     * 
     * @return the next token to be read
     * @throws IndexOutOfBoundsException if the stream is at the end
     */
    public String read() {
      if (isEndOfStream()) {
        throw new IndexOutOfBoundsException();
      }
      // post increment so that the index will advance after the currently
      // indexed value is read from
      return tokens[next++];
    }

    private int next;
    private final String[] tokens;
  }

  private static final String LEFT_PARENTHESIS = "(";
  private static final String PIPE_OPERATOR = "|";
  private static final String RIGHT_PARENTHESIS = ")";

  /**
   * Singleton representing any stop words in a query.
   */
  private static final Query STOPWORD_NODE = new Query() {
    public boolean matchesFilter(BitSet bloomFilter) {
      // Stop words never match anything
      return false;
    }

    public boolean matchesLineText(String lineText, CharacterAnalyzer analyzer) {
      // Stop words never match anything
      return false;
    }
  };

  public QueryParser(WordAnalyzer wordAnalyzer) {
    this.wordAnalyzer = wordAnalyzer;
  }

  /**
   * Parses a list of tokens as a Query.
   * 
   * @param tokens the list of tokens
   * @return a new Query
   * @throws QuerySyntaxError if the tokens cannot be parsed into a Query
   */
  public Query parseQuery(String[] tokens) throws QuerySyntaxError {
    // PRE: args is a non-null array
    TokenStream stream = new TokenStream(tokens);

    // Special case: an empty token stream is not a valid query.
    if (stream.isEndOfStream()) {
      throw new QuerySyntaxError();
    }

    // Stream is not at end, a PRE for parseTermList()
    Query result = parseTermList(stream);
    // Better be at the end of the stream!
    if (!stream.isEndOfStream()) {
      // This happens when there is an unmatched right parenthesis
      throw new QuerySyntaxError();
    }
    return result;
    // POST: if args represents a valid query, a Query is returned, otherwise
    // a QuerySyntaxError is thrown
  }

  /**
   * Parses token stream into an atom Query. An atom is either a word, or a
   * parenthetical expression.
   * 
   * @param stream the token stream
   * @return a new atom Query
   * @throws QuerySyntaxError if the tokens cannot be parsed into an atom
   */
  private Query parseAtom(TokenStream stream) throws QuerySyntaxError {
    // PRE: stream is a non-null list of tokens
    // PRE: we are not at the end of the stream already

    String nextToken = stream.read();

    if (nextToken.equals(LEFT_PARENTHESIS)) {
      // This is the start of a parenthetical expression
      // A parenthetical expression contains a term list and ends with a right
      // parenthesis.
      Query parenthetical = parseTermList(stream);

      // The POST of parseTermList guarantees that either the next token is a
      // right parenthesis, or the end of the stream has been reached. In the
      // latter case, that would indicate an unterminated parenthetical, which
      // would be a syntax error.
      if (stream.isEndOfStream()) {
        throw new QuerySyntaxError();
      }
      // Consume the right parenthesis (parseTermList did not)
      nextToken = stream.read();
      // ASSERT: nextToken.equals(RIGHT_PARENTHESIS)
      return parenthetical;
    } else if (nextToken.equals(RIGHT_PARENTHESIS)) {
      // This is a syntax error
      throw new QuerySyntaxError();
    } else if (nextToken.equals(PIPE_OPERATOR)) {
      // This is a syntax error
      throw new QuerySyntaxError();
    } else {
      // This is a word
      if (wordAnalyzer.isStopWord(nextToken)) {
        return STOPWORD_NODE;
      } else {
        return new WordNode(nextToken);
      }
    }

    // POST: if stream can be parsed as an atom, a Query is returned,
    // otherwise a QuerySyntaxError is thrown.
  }

  /**
   * Parses token stream into a term Query. A term is either an atom, or a
   * series of atoms all separated by pipes tokens. A term ends when the end of
   * the stream is reached, or if the token after the last atom we've processed
   * is not a pipe token.
   * 
   * @param stream the token stream
   * @return a new term Query
   * @throws QuerySyntaxError if the tokens cannot be parsed into a term
   */
  private Query parseTerm(TokenStream stream) throws QuerySyntaxError {
    // PRE: stream is a non-null list of tokens
    // PRE: we are not at the end of the stream already

    // Parse the first atom
    Query leftHandSide = parseAtom(stream);

    // Keep parsing until the stream ends or a non-pipe token is next
    while (!stream.isEndOfStream() && stream.peek().equals(PIPE_OPERATOR)) {
      // Consume the pipe token (peek didn't consume it)
      stream.read();
      // Parse the next atom
      Query rightHandSide = parseAtom(stream);
      // Each atom in a term is ORed together
      leftHandSide = new OrNode(leftHandSide, rightHandSide);
    }

    return leftHandSide;
    // POST: if stream can be parsed as a term, a Query is returned,
    // otherwise a QuerySyntaxError is thrown.
    // POST: either the stream is at the end, or the next token is not a pipe
    // token
  }

  /**
   * Parses token stream into a term list Query. A term list ends either when
   * the end of the stream is reached, or a right parenthesis is the next token.
   * 
   * @param stream the token stream
   * @return a new term list Query
   * @throws QuerySyntaxError if the tokens cannot be parsed into a term list
   */
  private Query parseTermList(TokenStream stream) throws QuerySyntaxError {
    // PRE: stream is a non-null list of tokens
    // PRE: we are not at the end of the stream already

    // Parse the first term
    Query leftHandSide = parseTerm(stream);

    // Keep parsing until stream ends or a right parenthesis is next
    while (!stream.isEndOfStream() && !stream.peek().equals(RIGHT_PARENTHESIS)) {
      // Parse the next term
      Query rightHandSide = parseTerm(stream);
      Query result;
      /*
       * TRICKY: Trying to AND a Stop Words cannot follow the normal algorithm.
       * Stop Words always return false for any line, so if we were to AND on a
       * Stop Word, it would effectively let a Stop Word trump the rest of the
       * query. This is not the desired behavior, so we have to special-case
       * this.
       * 
       * We don't have to do this trick with ORing because ORing gives us the
       * semantics we need.
       */
      if (leftHandSide == STOPWORD_NODE) {
        // strip out stop words
        result = rightHandSide;
      } else if (rightHandSide == STOPWORD_NODE) {
        // strip out stop words
        result = leftHandSide;
      } else {
        // Each term in a term list is ANDed together
        result = new AndNode(leftHandSide, rightHandSide);
      }
      leftHandSide = result;
    }
    return leftHandSide;
    // POST: if stream can be parsed as a term list, a Query is returned,
    // otherwise a QuerySyntaxError is thrown.
    // POST: either the stream is at the end, or the next token is a right
    // parenthesis
  }

  private final WordAnalyzer wordAnalyzer;
}
